package graphpaint;

import java.util.ArrayList;

public class Graph {
    static class Node{
        boolean painted=false;
        ArrayList<Integer> nodes=new ArrayList<Integer>();
        public Node() {
            
        }
        public void add(int n){
            nodes.add(n);
        }
    };

    private ArrayList<Node> lGraph=new ArrayList<Node>();
    private boolean[][] colours;
    private int count;

    public Graph() {
        
    }
    public void add(){
        lGraph.add(new Node());
    }
    public void addArc(int n, int m) {
        lGraph.get(n).add(m);
        lGraph.get(m).add(n);
    }
    private void paint(int n){
        int i=0;
        while(!colours[n][i]){
            i++;
        }
        lGraph.get(n).painted=true;
        if(i+1>count){
            count=i+1;
        }
        int nVert=lGraph.get(n).nodes.size();
        for(int j=0;j<nVert;j++){
            colours[lGraph.get(n).nodes.get(j)][i]=false;
        }
        for(int j=0;j<nVert;j++){
            if(!lGraph.get(lGraph.get(n).nodes.get(j)).painted){
                paint(lGraph.get(n).nodes.get(j));
            }
        }
    }
    public int getNum() {
        int nVert=lGraph.size();
        count = 0;
        colours=new boolean[nVert][nVert];
        for(int i=0;i<nVert;i++){
            for(int j=0;j<nVert;j++){
                colours[i][j]=true;
            }
        }
        for(int i=0;i<nVert;i++){
            lGraph.get(i).painted=false;
        }
        paint(0);
        return count;
    }
}
